#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <string>
#include <stdbool.h>
#include <cstdio>


// 前序中序还原二叉树
// https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
//class Solution {
//public:
//    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& persub, int inbegin, int inend) {
//        if (inbegin > inend) {
//            return nullptr;
//        }
//
//
//        TreeNode* Node = new TreeNode(preorder[persub]);
//
//
//        int iroot = inbegin;
//        while (iroot <= inend) {
//            if (preorder[persub] == inorder[iroot]) {
//                break;
//            }
//            else {
//                ++iroot;
//            }
//        }
//        ++persub;
//        Node->left = _buildTree(preorder, inorder, persub, inbegin, iroot - 1);
//        Node->right = _buildTree(preorder, inorder, persub, iroot + 1, inend);
//
//
//        return Node;
//
//
//    }
//    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//        int persub = 0;
//        return _buildTree(preorder, inorder, persub, 0, inorder.size() - 1);
//    }
//};

// 中序和后序还原二叉树
// https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
//class Solution {
//public:
//    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& persub, int inbegin, int inend) {
//        if (inbegin > inend)
//            return nullptr;
//
//
//        TreeNode* Node = new TreeNode(postorder[persub]);
//
//
//        int iroot = inend;
//        while (iroot >= 0)
//        {
//            if (postorder[persub] == inorder[iroot])
//                break;
//            else
//                --iroot;
//        }
//
//
//        --persub;
//        Node->right = _buildTree(inorder, postorder, persub, iroot + 1, inend);
//        Node->left = _buildTree(inorder, postorder, persub, inbegin, iroot - 1);
//        return Node;
//    }
//
//
//    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
//        int persub = postorder.size() - 1;
//        return _buildTree(inorder, postorder, persub, 0, inorder.size() - 1);
//    }
//};


// 二叉树前序非递归遍历
// https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
//class Solution {
//public:
//    vector<int> preorderTraversal(TreeNode* root) {
//        if (!root) return vector<int>();
//        vector<int> v;
//
//
//        stack<TreeNode*> st;
//        st.push(root);
//
//
//        while (!st.empty())
//        {
//            TreeNode* node = st.top();
//            st.pop();
//            if (node)
//            {
//                v.push_back(node->val);
//                st.push(node->right);//右节点先进，后续如果左节点没有遍历完右节点会一直被压在栈中
//                st.push(node->left);
//            }
//        }
//        return v;
//    }
//};


//二叉树的中序非递归遍历
//https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/
//class Solution {
//public:
//    vector<int> inorderTraversal(TreeNode* root) {
//        if (!root) return vector<int>();
//        vector<int> v;
//        stack<TreeNode*> st;
//
//        TreeNode* cur = root;
//        while (cur || !st.empty())
//        {
//            while (cur)
//            {
//                st.push(cur);
//                cur = cur->left;
//            }
//
//            TreeNode* node = st.top();
//            st.pop();
//            v.push_back(node->val);
//            cur = node->right;
//        }
//        return v;
//    }
//};


//二叉树后序非递归遍历
//https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/
//class Solution {
//public:
//    // vector<int> postorderTraversal(TreeNode* root) {
//    //     vector<int> v;
//    //     if(!root) return v;
//    //     stack<TreeNode*> st;
//
//
//    //     //解法一
//    //     TreeNode* cur = root;
//    //     //TreeNode* prev = nullptr;
//    //     while(cur || !st.empty())
//    //     {
//    //         while(cur)
//    //         {
//    //             st.push(cur);
//    //             cur = cur -> left; //遍历左路节点
//    //         }
//
//    //         TreeNode* node = st.top();
//    //         //if(!node->right || node->right == prev) //判断是一个访问的右节点是否已经访问
//    //         if(!node->right || (node->right && !v.empty() && node->right->val==v.back())) //检查上一个右子树是否已经访问，如果已经访问则会在vector最末尾
//    //         {
//    //             //prev = node;
//    //             v.push_back(node->val);
//    //             st.pop();
//    //         }
//    //         else
//    //         {
//    //             cur = node->right;
//    //         }
//    //     }
//    //     return v;
//    // }
//
//    //解法二
//    vector<int> postorderTraversal(TreeNode* root) {
//        vector<int> v;
//        if (!root) return v;
//        stack<TreeNode*> st;
//        st.push(root);
//
//        //层序遍历逆置
//        while (!st.empty())
//        {
//            TreeNode* node = st.top();
//            st.pop();
//            v.push_back(node->val);
//            if (node->left)
//                st.push(node->left);
//            if (node->right)
//                st.push(node->right);
//        }
//        reverse(v.begin(), v.end());
//        return v;
//    }
//};